import java.util.ArrayList;


public class SortingMethods {
	static int[] ints;

	SortingMethods(){
		ints = new int[3];
	}

	public static void bubbleSort1() {
		int n = ints.length;
		for (int pass=1; pass < n; pass++) {
			for (int i=0; i < n-pass; i++) {
				if (ints[i] > ints[i+1]) {
					int temp = ints[i];  ints[i] = ints[i+1];  ints[i+1] = temp;
				}
			}
		}
	}

	public static void selectionSort1(int[] ints) {
		for (int i=0; i<ints.length-1; i++) {
			for (int j=i+1; j<ints.length; j++) {
				if (ints[i] > ints[j]) {
					int temp = ints[i];
					ints[i] = ints[j];
					ints[j] = temp;
				}
			}
		}
	}

	public static void InsertionSort()
	{
		int j, key, i;

		for (j = 1; j < ints.length; j++)
		{
			key = ints[j];
			for(i = j - 1; (i >= 0) && (ints[i] < key); i--)
			{
				ints[i+1] = ints[i];
			}
			ints[i+1] = key;
		}
	}

	/**
     * Mergesort algorithm.
     * @param a an array of Comparable items.
     */
    public static void mergeSort() {
        int[] tmpArray = new int[ ints.length ];
        mergeSort( ints, tmpArray, 0, ints.length - 1 );
    }
    
    /**
     * Internal method that makes recursive calls.
     * @param a an array of Comparable items.
     * @param tmpArray an array to place the merged result.
     * @param left the left-most index of the subarray.
     * @param right the right-most index of the subarray.
     */
    private static void mergeSort( int[]a, int[]tmpArray,int left, int right ) {
        if( left < right ) {
            int center = ( left + right ) / 2;
            mergeSort( a, tmpArray, left, center );
            mergeSort( a, tmpArray, center + 1, right );
            merge( a, tmpArray, left, center + 1, right );
        }
    }
    
    /**
     * Internal method that merges two sorted halves of a subarray.
     * @param a an array of Comparable items.
     * @param tmpArray an array to place the merged result.
     * @param leftPos the left-most index of the subarray.
     * @param rightPos the index of the start of the second half.
     * @param rightEnd the right-most index of the subarray.
     */
    private static void merge( int[]a, int[]tmpArray, int leftPos, int rightPos, int rightEnd ) {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;
        
        // Main loop
        while(leftPos <= leftEnd && rightPos <= rightEnd)
            if( a[leftPos]<=a[rightPos])
                tmpArray[tmpPos++] = a[leftPos++];
            else
                tmpArray[tmpPos++] = a[rightPos++];
        
        while(leftPos <= leftEnd)    // Copy rest of first half
            tmpArray[tmpPos++] = a[leftPos++];
        
        while(rightPos <= rightEnd)  // Copy rest of right half
            tmpArray[tmpPos++] = a[rightPos++];
        
        // Copy tmpArray back
        for(int i = 0; i < numElements; i++, rightEnd--)
            a[rightEnd] = tmpArray[rightEnd];
    }
}
